package com.kyle.java.sorting;


import kyleUtil.dateFormat.TimeRecorder;

import java.util.Arrays;

/**
 * @author kyle
 * @version 1.0
 * @date 2021/4/7 13:58
 *
 *
 *  选择排序：
 *  举例：从小到大排序
 *  思想： 每一轮找到最小的那个元素，让这个元素和 第 i 轮的元素进行交换
 *
 *  数组    { 9,1,4,2,3 }
 *
 *  第一轮： 1.找到 最小元素 1
 *         2.将1放在第[0]个位置
 *         3.{1,9,4,2,3}
 *
 *  第二轮 ：1 {1,,9,4,2,3}
 *         2  找到最小元素2
 *         3. 将2放在第1个位置
 *         4{1,2,4,9,3}
 */

public class SelectSorting {

    public static void main(String[] args) {
        int[] array = new int[150000];

        for(int i = 0 ;i<array.length;i++){
            array[i] = (int)(Math.random()*200000) +1;  //产生从1 - 10000的随机数
        }

        int[] copiedArray = Arrays.copyOf(array,array.length); //拷贝数组，以让冒泡排序用同样数组进行排序

        TimeRecorder timeRecorder1 = new TimeRecorder(); //记录选择排序时间
        TimeRecorder timeRecorder2 = new TimeRecorder(); //记录冒泡排序时间
        TimeRecorder timeRecorder3 = new TimeRecorder(); //记录插入排序时间
        //开始选择排序
        timeRecorder1.beginRecord();
        intArraySelectSortingASC(array);
        timeRecorder1.endRecord();
        //结束选择排序

        //开始冒泡排序//
        timeRecorder2.beginRecord();
        BubbleSorting.intArrayBubbleSortingASC(copiedArray);
        timeRecorder2.endRecord();
        //结束冒泡排序

        //开始插入排序//
        timeRecorder3.beginRecord();
        InsertSorting.intArrayInsertSortingASC(copiedArray);
        timeRecorder3.endRecord();
        //结束插入排序

        System.out.println("-----------------------------------");
        System.out.println("选择排序时间");
        timeRecorder1.print();
        System.out.println("-----------------------------------");
        System.out.println("-----------------------------------");
        System.out.println("冒泡排序时间");
        timeRecorder2.print();
        System.out.println("-----------------------------------");

        System.out.println("-----------------------------------");
        System.out.println("插入排序时间");
        timeRecorder3.print();
        System.out.println("-----------------------------------");

    }
    public static void intArraySelectSortingASC(int[] array) {
              for(int i = 0 ; i < array.length-1 ; i++) //找到 从头到 array.length - 1个 下标对应的元素
              {
                  int min = array[i]; //将第i小元素的起始元素置为min
                  int min_index = i;
                  for(int j = i; j < array.length;j++){  //每一轮找到第i小的元素
                      if(array[j] < min){  //如果找到比当前记录元素更小的元素
                          min = array[j];  //记录元素和下标
                          min_index = j;
                      }
                  }
                  if(min_index!=i){ //如果发生了交换则
                      int temp = array[i];
                      array[i] = array[min_index];
                      array[min_index] = temp;
                  }
              }

    }
}
